Non-Markovian decoherent quantum walks

Quantum walks act in obviously different ways from their classical counterparts, but decoherence will lessen and close this gap between them. To understand this process, it is necessary to investigate the evolution of quantum walks under different decoherence situations. In this article, we study a non-Markovian decoherent quantum walk on a line. In a short time regime, the behavior of the walk deviates from both ideal quantum walks and classical random walks. The position variance as a measure of the quantum walk collapses and revives for a short time, and tends to have a linear relation with time. That is, the walker's behavior shows a diffusive spread over a long time limit, which is caused by non-Markovian dephasing affecting the quantum correlations between the quantum walker and his coin. We also study both quantum discord and measurement-induced disturbance as measures of the quantum correlations, and observe both collapse and revival in the short time regime, and the tendency to be zero in the long time limit. Therefore, quantum walks with non-Markovian decoherence tend to have diffusive spreading behavior over long time limits, while in the short time regime they oscillate between ballistic and diffusive spreading behavior, and the quantum correlation collapses and revives due to the memory effect.     

Topological Properties of Fibonacci Networks

The Fibonacci numbers are the numbers defined by the linear recurrence equation,in which each subsequent number is the sum of the previous two.In this paper,we propose Fibonacci networks using Fibonacci numbers.The analytical expressions involving degree distribution,average path length and mean first passage time are obtained.This kind of networks exhibits the small-world characteristic and follows the exponential distribution.Our proposed models would provide the valuable insights into the deterministically delayed growing networks.     

Hyperfinite Lévy Processes

A hyperfinite Lévy process is an infinitesimal random walk (in the sense of nonstandard analysis) which with probability one is finite for all finite times. We develop the basic theory for hyperfinite Lévy processes and find a characterization in terms of transition probabilities. The standard part of a hyperfinite Lévy process is a (standard) Lévy process, and we show that given a generating triplet (γ, C, μ) for standard Lévy processes, we can construct hyperfinite Lévy processes whose standard parts correspond to this triplet. Hence all Lévy laws can be obtained from hyperfinite Lévy processes. The paper ends with a brief look at Malliavin calculus for hyperfinite Lévy processes including a version of the Clark-Haussmann-Ocone formula.     

Families of prudent self-avoiding walks

A self-avoiding walk (SAW) on the square lattice is prudent if it never takes a step towards a vertex it has already visited. Prudent walks differ from most classes of SAW that have been counted so far in that they can wind around their starting point.Their enumeration was first addressed by Préa in 1997. He defined 4 classes of prudent walks, of increasing generality, and wrote a system of recurrence relations for each of them. However, these relations involve more and more parameters as the generality of the class increases.The first class actually consists of partially directed walks, and its generating function is well known to be rational. The second class was proved to have an algebraic (quadratic) generating function by Duchi (2005). Here, we solve exactly the third class, which turns out to be much more complex: its generating function is not algebraic, nor even D-finite.The fourth class—general prudent walks—is the only isotropic one, and still defeats us. However, we design an isotropic family of prudent walks on the triangular lattice, which we count exactly. Again, the generating function is proved to be non-D-finite.We also study the asymptotic properties of these classes of walks, with the (somewhat disappointing) conclusion that their endpoint moves away from the origin at a positive speed. This is confirmed visually by the random generation procedures we have designed.     

Path-integral solution of the one-dimensional Dirac quantum cellular automaton

Quantum cellular automata, which describe the discrete and exactly causal unitary evolution of a lattice of quantum systems, have been recently considered as a fundamental approach to quantum field theory and a linear automaton for the Dirac equation in one dimension has been derived. In the linear case a quantum cellular automaton is isomorphic to a quantum walk and its evolution is conveniently formulated in terms of transition matrices. The semigroup structure of the matrices leads to a new kind of discrete path-integral, different from the well known Feynman checkerboard one, that is solved analytically in terms of Jacobi polynomials of the arbitrary mass parameter.     

Tail estimates for one-dimensional non-nearest-neighbor random walk in random environment

Suppose that the integers are assigned i.i.d. random variables {(β gx , . . . , β 1x , α x )} (each taking values in the unit interval and the sum of them being 1), which serve as an environment. This environment defines a random walk {X n } (called RWRE) which, when at x, moves one step of length 1 to the right with probability α x and one step of length k to the left with probability β kx for 1≤ k≤ g. For certain environment distributions, we determine the almost-sure asymptotic speed of the RWRE and show that the chance of the RWRE deviating below this speed has a polynomial rate of decay. This is the generalization of the results by Dembo, Peres and Zeitouni in 1996. In the proof we use a large deviation result for the product of random matrices and some tail estimates and moment estimates for the total population size in a multi-type branching process with random environment.     

Trees, unicyclic graphs and bicyclic graphs with exactly two Q-main eigenvalues

The signless Laplacian matrix of a graph G is defined to be the sum of its adjacency matrix and degree diagonal matrix, and its eigenvalues are called Q-eigenvalues of G. A Q-eigenvalue of a graph G is called a Q-main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero. In this work, all trees, unicyclic graphs and bicyclic graphs with exactly two Q-main eigenvalues are determined.     

Scaling of Loop-Erased Walks in 2 to 4 Dimensions

We simulate loop-erased random walks on simple (hyper-)cubic lattices of dimensions 2, 3 and 4. These simulations were mainly motivated to test recent two loop renormalization group predictions for logarithmic corrections in d=4, simulations in lower dimensions were done for completeness and in order to test the algorithm. In d=2, we verify with high precision the prediction D=5/4, where the number of steps n after erasure scales with the number N of steps before erasure as n∼N ^D/2. In d=3 we again find a power law, but with an exponent different from the one found in the most precise previous simulations: D=1.6236±0.0004. Finally, we see clear deviations from the naive scaling n∼N in d=4. While they agree only qualitatively with the leading logarithmic corrections predicted by several authors, their agreement with the two-loop prediction is nearly perfect.     

Exact solutions of lattice polymer models

We consider directed path models of a selection of polymer and vesicle problems. Each model is used to illustrate an important method of solving lattice path enumeration problems. In particular, the Temperley method is used for the polymer collapse problem. The ZL method is used to solve the semi-continuous vesicle model. The Constant Term method is used to solve a set of partial difference equations for the polymer adsorption problem. The Kernel method is used to solve the functional equation that arises in the polymer force problem. Finally, the Transfer Matrix method is used to solve a problem in colloid dispersions. All these methods are combinatorially similar as they all construct equations by considering the action of adding an additional column to the set of objects.     

Gene flow across geographical barriers — scaling limits of random walks with obstacles

We study a class of random walks which behave like simple random walks outside of a bounded region around the origin and which are subject to a partial reflection near the origin. We obtain a non trivial scaling limit which behaves like reflected Brownian motion until its local time at zero reaches an exponential variable. It then follows reflected Brownian motion on the other side of the origin until its local time at zero reaches another exponential level, etc. These random walks are used in population genetics to trace the position of ancestors in the past near geographical barriers.